package com.xizi.剑指offer;

import java.util.Deque;

public class 构建乘积数组 {

    public static void main(String[] args) {
        int[] multiply = multiply(new int[]{1, 2, 3, 4, 5});
        for (int i = 0; i < multiply.length; i++) {
            System.out.print(multiply[i] + " ");
        }
    }

    public static int[] multiply(int[] A) {
        int n = A.length;
        int[] res = new int[n];
        //前缀乘
        //A[]    1 2 3 4 5
        //res[]  1 1 2 6 24
        for (int i = 0, t = 1; i < n; t *= A[i], i++) {
            res[i] = t;
        }
        //res[]
        for (int i = n - 1, t = 1; i >= 0; t *= A[i], i--) {
            res[i] *= t;
        }
        return res;
    }
}
